package pers.qianyu.month_202011.date_20201118;

import java.util.*;

/**
 * 986. 区间列表的交集
 * https://leetcode-cn.com/problems/interval-list-intersections/
 *
 * @author mizzle rain
 * @date 2020-11-18 13:59
 */
public class IntervalIntersection {
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        int pa = 0, pb = 0;
        ArrayList<int[]> res = new ArrayList<>();
        while (pa < A.length && pb < B.length) {
            int[] curA = A[pa];
            int[] curB = B[pb];
            if (!((curA[1] < curB[0]) || (curA[0] > curB[1]))) {
                // 有交集
                res.add(new int[]{Math.max(curA[0], curB[0]), Math.min(curA[1], curB[1])});
            }
            if (curA[1] > curB[1]) {
                pb++;
            } else if (curA[1] < curB[1]) {
                pa++;
            } else {
                pa++;
                pb++;
            }
        }
        return res.toArray(new int[0][0]);
    }

    public static void main(String[] args) {
        int[][] param1 = {{0, 2}, {5, 10}, {13, 23}, {24, 25}};
        int[][] param2 = {{1, 5}, {8, 12}, {15, 24}, {25, 26}};
        int[][] result = new IntervalIntersection().intervalIntersection(param1, param2);
        System.out.println("result = " + Arrays.deepToString(result));
    }
}
